package seven.test_7_16;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public void permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        for (int i = 0; i < ret.size(); i++) {
            if(isThree(ret.get(i))) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
    private boolean isThree(List<Integer> path) {
        if((path.get(0) + path.get(1) > path.get(2)) && (path.get(3) + path.get(4) > path.get(5))) {
            if((Math.abs(path.get(0) - path.get(1)) < path.get(2)) && (Math.abs(path.get(3) - path.get(4)) < path.get(5))) {
                return true;
            }
        }
        return false;
    }
    private void dfs(int[] nums) {
        if(nums.length == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(check[i] == false) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回溯 -> 恢复现场
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    //
    public int MLS(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;
        int longest = 1;//记录最长的有序序列
        int count = 1;//目前有序序列的长度
        //先对数组进行排序
        Arrays.sort(arr);
        for (int i = 1; i < arr.length; i++) {
            //跳过重复的
            if (arr[i] == arr[i - 1])
                continue;
            //比前一个大1，可以构成连续的序列，count++
            if ((arr[i] - arr[i - 1]) == 1) {
                count++;
            } else {
                //没有比前一个大1，不可能构成连续的，
                //count重置为1
                count = 1;
            }
            //记录最长的序列长度
            longest = Math.max(longest, count);
        }
        return longest;
    }
}
